package com.yiwenup.sorting._08_couting;

import com.yiwenup.sorting.base.Sort;

/**
 * 计数排序：针对一定范围的整数排序（优化之前的空间浪费、无法处理负数、不稳定的问题）
 * 时间复杂度：最好 - O(n+k)；最坏 - O(n+k)；平均复杂度 - (n+k)【k指代范围】
 * 空间复杂度：O(n+K)
 * 稳定性：稳定
 **/
public class CountingSortV2 extends Sort<Integer> {
    @Override
    protected void work() {
        // 1. 找到最大值/最小值，确定开辟范围
        int max = array[0];
        int min = array[0];
        for (int i = 1; i < array.length; i++) {
            if (array[i] > max) {
                max = array[i];
            }
            if (array[i] < min) {
                min = array[i];
            }
        }
        // 2.开辟内存空间
        int[] counts = new int[max - min + 1];

        // 3.统计每个元素出现的次数
        for (int i = 0; i < array.length; i++) {
            counts[array[i] - min]++;
        }

        // 4.次数累加
        for (int i = 1; i < counts.length; i++) {
            counts[i] += counts[i - 1];
        }

        // 5.遍历（从后往前，可以保证稳定性）
        int[] newArray = new int[array.length];
        for (int i = array.length - 1; i >= 0; i--) {
            newArray[--counts[array[i] - min]] = array[i];
        }

        // 6.有序数组覆盖
        for (int i = 0; i < newArray.length; i++) {
            array[i] = newArray[i];
        }
    }
}
